package com.example.arithmeticleetcode.learnArithmetic2.union;

/**
 * @program: arithmetic-leetcode
 * @description:
 * @author: FangZhen
 * @create: 2020-11-12 13:42
 **/
public class UnionFind_QF  extends UnionFind{

    public UnionFind_QF(int capacity) {
        super(capacity);
    }

    /**
     * 查找v所属的集合 O(1)
     *
     * @param v
     * @return
     */
    @Override
    public int find(int v) {
        rangeCheck(v);
        return parents[v];
    }

    /**
     * 合并 O(n)
     *
     * @param v1
     * @param v2
     */
    @Override
    public void union(int v1, int v2) {
        int p1 = find(v1);
        int p2 = find(v2);
        if (p1 == p2) return;
        for (int i = 0, len = parents.length; i < len; i++) {
            if (parents[i] == p1) {
                parents[i] = p2;
            }
        }
    }




}
